//给定两个大小为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。 
//
// 请你找出这两个正序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。 
//
// 你可以假设 nums1 和 nums2 不会同时为空。 
//
// 
//
// 示例 1: 
//
// nums1 = [1, 3]
//nums2 = [2]
//
//则中位数是 2.0
// 
//
// 示例 2: 
//
// nums1 = [1, 2]
//nums2 = [3, 4]
//
//则中位数是 (2 + 3)/2 = 2.5
// 
// Related Topics 数组 二分查找 分治算法 
// 👍 3033 👎 0

package leetcode.editor.cn;

//Java：寻找两个正序数组的中位数
public class P4MedianOfTwoSortedArrays {

    //leetcode submit region begin(Prohibit modification and deletion)
    /**
     * 思路： 维护两个指针，判断各自数组的指针所指的数据大小，小的，加到新的数组中，指针往右移，加完停止
     *
     * 执行用时： 3 ms , 在所有 Java 提交中击败了 62.17% 的用户 内存消耗： 41 MB , 在所有 Java 提交中击败了 20.58% 的用户
     */
    class Solution {
        public double findMedianSortedArrays(int[] nums1, int[] nums2) {
            int[] array = combine(nums1, nums2);
            double a;
            if (array.length % 2 == 1) {
                a = array[(array.length - 1) / 2];
            } else {
                a = ((double) (array[array.length / 2] + array[array.length / 2 - 1])) / 2;
            }
            return a;
        }

        private int[] combine(int[] a1, int[] a2) {
            int i = a1.length;
            int k = a2.length;
            int length = i + k;
            int[] array = new int[length];

            int left = 0;
            int right = 0;
            int now = 0;
            while (now < length) {
                if (left >= i) {
                    array[now] = a2[right];
                    now++;
                    right++;
                } else if (right >= k) {
                    array[now] = a1[left];
                    now++;
                    left++;
                } else {
                    if (a1[left] <= a2[right]) {
                        array[now] = a1[left];
                        left++;
                        now++;
                    } else {
                        array[now] = a2[right];
                        right++;
                        now++;
                    }
                }
            }
            return array;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)

    public static void main(String[] args) {
        Solution solution = new P4MedianOfTwoSortedArrays().new Solution();
        int[] a1 = new int[]{1,3,4};
        int[] a2 = new int[]{2,4,5};
        System.out.println(solution.findMedianSortedArrays(a1,a2));
        // TO TEST
    }

}